// 相对于防御导弹的题目，该系统能够自由选择下降或者上升
// 每次应该选择进入下降队列或者上升队列没有一个很好的策略能够进行判断选择
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 55, INF = 1e9;
int up[N], down[N], h[N];
int n, res;

// t表示当前正在dfs的数量，upl表示当前上升子序列的长度，downl表示当前下降子序列的长度
void dfs(int t, int upl, int downl)
{
    // 如果当前总共所需的系统数量已经大于答案数了，那就没有必要继续递归了，直接剪枝
    if (upl + downl >= res)
        return;
    if (t == n + 1)
        res = upl + downl; // 表示所有导弹都被成功拦截，跟新答案
    // 情况1：放在上升炮台序列中
    int l = 0, r = upl;
    // 在递减序列中找到不大于h[t]的最大值
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (up[mid] > h[t])
            l = mid + 1;
        else
            r = mid;
    }
    int tmp = up[l];
    bool is_change = false, new_bar = false;
    // 出循环后，判断是否需要新开一个炮台
    if (up[l] > h[t])
        up[++upl] = h[t], new_bar = true;
    else
        up[l] = h[t], is_change = true;
    dfs(t + 1, upl, downl);
    // dfs递归结束要恢复原样
    if (is_change)
        up[l] = tmp, is_change = false;
    if (new_bar)
        --upl;
    // 情况2：放在下降炮台序列中
    l = 0, r = downl;
    // 每次找到不小于h[t]的最小值
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (down[mid] < h[t])
            l = mid + 1;
        else
            r = mid;
    }
    tmp = down[l];
    is_change = false, new_bar = false;
    if (down[l] < h[t])
        down[++downl] = h[t], new_bar = true;
    else
        down[l] = h[t], is_change = true;
    dfs(t + 1, upl, downl);
    if (is_change)
        down[l] = tmp;
    if (new_bar)
        --downl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    while (cin >> n, n)
    {
        // 最坏的情况下每发导弹需要一个系统
        res = n;
        up[0] = INF;
        for (int i = 1; i <= n; ++i)
            cin >> h[i];
        dfs(1, 0, 0);
        cout << res << endl;
    }
    return 0;
}